package method;

/**
 * @author yuisama
 * @date 2022/08/22 09:46
 * 递归实现汉诺塔
 **/
public class HanoiTower {
    static int count;
    public static void main(String[] args) {
        int n = 3;
        hanoiTower(n,'A','B','C');
        System.out.println("总共移动了" + count + "次");
    }

    /**
     * 将A上这个nDisks从A移动到C上
     * @param nDisks 盘子编号从上到下依次为1 .. n
     * @param A
     * @param B
     * @param C
     */
    public static void hanoiTower(int nDisks,char A,char B,char C) {
        // 1.边界
        if (nDisks == 1) {
            move(1,A,C);
            return;
        }
        // a.先将A上的n - 1个盘子从A塔移动到B塔，C塔暂存小盘子
        hanoiTower(nDisks - 1,A,C,B);
        // b.只需要将A上最大的这个盘子n，从A -> C
        move(nDisks,A,C);
        // c.最后再将B上的这n - 1个盘子从B塔移动到C塔，A塔暂存小盘子
        hanoiTower(nDisks - 1,B,A,C);
    }

    /**
     * 将编号为n的盘子从源塔sourceTower移动到目标塔distTower
     * @param nDisks
     * @param sourceTower
     * @param distTower
     */
    public static void move(int nDisks,char sourceTower,char distTower) {
        System.out.println("正在将编号为" + nDisks + "的盘子从" + sourceTower + "->" + distTower);
        count ++;
    }
}